package com.fengye.algorithms.leecode;

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/search-a-2d-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author fengye
 * @Date 2023/4/21 6:09
 **/
public class SearchA2dMatrix74 {

    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        System.out.println(new SearchA2dMatrix74().searchMatrix(matrix, 3));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;

        if(target < matrix[0][0] || target > matrix[row-1][col - 1]) {
            return false;
        }
        for(int i=0;i<row;i++) {
            int rs = matrix[i][0];
            int re = matrix[i][col-1];
            if(rs == target) {
                return true;
            }
            /**
             * 先找出区间，在二分搜索
             */
            if(rs < target && target < re) {
                return search(matrix[i], target) > 0;
            }

            if(re == target) {
                return true;
            }
        }

        return false;
    }

    public int search(int[] nums, int target) {
        int n = nums.length;
        if(nums[n-1] < target) {
            return -1;
        }
        if(nums[0] > target) {
            return -1;
        }

        int start = 0;
        int end = n-1;
        while(start<=end) {
            int mid = (end+start)/2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] > target) {
                end = mid-1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

}
